/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/backpack-v
   @Language: C++
   @Datetime: 20-01-15 11:12
   */

// Method 1
class Solution {
public:
	/**
	 * @param nums: an integer array and all positive numbers
	 * @param target: An integer
	 * @return: An integer
	 */
	int backPackV(vector<int> &nums, int target) {
		// write your code here
		vector<int> dp(target+1);
		dp[0]=1;
		for(int i=0; i<nums.size(); ++i)
			for(int j=target; j>=nums[i]; --j)
				dp[j]+=dp[j-nums[i]];
		return dp[target];
	}
};


// Method 2
class Solution {
public:
	/**
	 * @param nums: an integer array and all positive numbers
	 * @param target: An integer
	 * @return: An integer
	 */
	int backPackV(vector<int> &nums, int target) {
		// write your code here
		vector<int> dp(target+1);
		dp[0]=1;
		int sum=0;
		for(int i=0; i<nums.size(); ++i){
			sum+=nums[i];
			for(int j=min(sum,target); j>=nums[i]; --j)
				dp[j]+=dp[j-nums[i]];
		}
		return dp[target];
	}
};
